package com.smh;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

/**
 * @author shiminghui
 * @date 2025/3/19 20:29
 * @description: TODO
 */
public class _068_至少k个重复字符 {

    /**
     * 给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
     * 如果不存在这样的子字符串，则返回 0。
     */

    @Test
    public void test1() {
        System.out.println(longestSubstring("aaabb", 3));
    }

    public int longestSubstring(String s, int k) {

        if (s.length() < k) {
            return 0;
        }

        // 通过计数法,找到不满足条件的字符
        int[] chars = new int[128];
        char[] charArray = s.toCharArray();
        for (char c : charArray) {
            chars[c]++;
        }
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] > 0 && chars[i] < k) {
                set.add((char) i);
            }
        }
        ArrayList<String> list = new ArrayList<>();
        // 然后根据这些字符进行分割
        if (set.isEmpty()) {
            return s.length();
        } else {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < charArray.length; i++) {
                if (set.contains(charArray[i])) {
                    if (!sb.isEmpty()) {
                        list.add(sb.toString());
                        sb.setLength(0);
                    }
                } else {
                    sb.append(charArray[i]);
                }
            }
            if (!sb.isEmpty()) {
                list.add(sb.toString());
            }
            int max = 0;
            for (String str : list) {
                max = Math.max(max, longestSubstring(str, k));
            }
            return max;
        }
    }

}
